#pragma once
#include "ProtoVanEmdeBoasTree.h"

template <size_t K>
bool ProtoVanEmdeBoas<K>::member(size_t x) const
{
	if (x >= u)
		return false;

	const Cld* pCld = cluster[high(x)];
	if (!pCld)
		return false;

	return pCld->member(low(x));
}

template <size_t K>
auto ProtoVanEmdeBoas<K>::min() const->std::optional<size_t>
{
	if (!summary)
		return std::nullopt;

	auto m = summary->min();
	if (!m || *m >= Cld::u)
		return std::nullopt;

	const Cld* pCld = cluster[*m];
	if (!pCld)
		return std::nullopt;

	auto offset = pCld->min();
	if (!offset)
		return std::nullopt;

	return index(*m, *offset);
}

template <size_t K>
auto ProtoVanEmdeBoas<K>::successor(size_t x) const->std::optional<size_t>
{
	size_t highX = high(x);
	const Cld* pCld = cluster[highX];
	if (!pCld)
		return std::nullopt;

	auto offset = pCld->successor(low(x));
	if (offset)
		return index(highX, *offset);

	if (!summary)
		return std::nullopt;

	auto nextCld = summary->successor(highX);
	if (!nextCld || *nextCld >= Cld::u)
		return std::nullopt;

	const Cld* pNextCld = cluster[*nextCld];
	if (!pNextCld)
		return std::nullopt;

	offset = pNextCld->min();
	if (!offset)
		return std::nullopt;

	return index(*nextCld, *offset);
}

template <size_t K>
bool ProtoVanEmdeBoas<K>::insert(size_t x)
{
	if (x >= u)
		return false;

	size_t highX = high(x);
	if (!summary)
		summary = new Cld;

	if (!summary)
		return false;
		
	Cld*& pCld = cluster[highX];
	if (!pCld)
		pCld = new Cld;

	if (!pCld)
		return false;

	summary->insert(highX);
	pCld->insert(low(x));
	return true;
}

